package com.yequan.leetcode.array.longestpalindrome;

import java.util.HashSet;

/**
 * //给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
 * //
 * // 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
 * //
 * // 注意:
 * //假设字符串的长度不会超过 1010。
 * //
 * // 示例 1:
 * //
 * //
 * //输入:
 * //"abccccdd"
 * //
 * //输出:
 * //7
 * //
 * //解释:
 * //我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * //
 * // Related Topics 哈希表
 *
 * @author : Administrator
 * @date : 2020/3/19
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        String s = "abccccdd";
        LongestPalindrome longestPalindrome = new LongestPalindrome();
        int count = longestPalindrome.longestPalindrome4(s);
        System.out.println(count);
    }

    /**
     * 奇数统计法
     * 1.统计所有字符出现的次数
     * 2.根据次数找出奇数次的字符
     * 3.字符串长度减去奇数次+1(如果奇数次>0,否则不加)
     * <p>
     * 复杂度:
     * 时间复杂度: O(n)
     * 空间复杂度: O(s)
     *
     * @param s
     * @return
     */
    public int longestPalindrome1(String s) {
        int[] countArray = count(s);
        int oddCount = findOddNumCharCount(countArray);
        return s.length() - oddCount + (oddCount > 0 ? 1 : 0);
    }

    private int findOddNumCharCount(int[] countArray) {
        int oddCount = 0;
        for (int i : countArray) {
            if (i % 2 == 1) {
                oddCount++;
            }
        }
        return oddCount;
    }

    private int[] count(String s) {
        int[] count = new int[58];
        s.chars().forEach(c -> ++count[c - 'A']);
        return count;
    }

    /**
     * 贪心法
     * 1.统计所有字符串出现的次数
     * 2.统计所有偶数次出现的次数,并将第一个出现奇数次的字符次数加1
     *
     * @param s
     * @return
     */
    public int longestPalindrome2(String s) {
        int[] countArray = new int[58];
        s.chars().forEach(c -> ++countArray[c - 'A']);

        int length = 0;
        for (int count : countArray) {
            //如果i是偶数,统计次数不变,计入回文串中
            //如果i是奇数,则第一次出现的奇数计入回文串中作为回文中心,以后的奇数次不再计入 则统计计入的回文次数为 count-1
            length += count / 2 * 2;
            if (count % 2 == 1 && length % 2 == 0) {
                length++;
            }
        }
        return length;
    }

    /**
     * 贪心法
     * 1.统计所有字符串出现的次数
     * 2.统计所有偶数次出现的次数,并将第一个出现奇数次的字符次数加1
     *
     * @param s
     * @return
     */
    public int longestPalindrome3(String s) {
        int[] countArray = new int[58];
        s.chars().forEach(c -> ++countArray[c - 'A']);

        int length = 0;

        for (int count : countArray) {
            //只取偶数个
            length += count - (count & 1);
        }
        return length < s.length() ? length + 1 : length;
    }

    public int longestPalindrome4(String s) {
        if (s == null || s.length() == 0) return 0;
        HashSet<Character> hs = new HashSet<Character>();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (hs.contains(s.charAt(i))) {
                hs.remove(s.charAt(i));
                count++;
            } else {
                hs.add(s.charAt(i));
            }
        }
        if (!hs.isEmpty()) return count * 2 + 1;
        return count * 2;
    }

}
